﻿#include "../exercise.h"
#include <vector>

// READ: std::vector <https://zh.cppreference.com/w/cpp/container/vector_bool>
// READ: 模板特化 <https://zh.cppreference.com/w/cpp/language/template_specialization>

// TODO: 将下列 `?` 替换为正确的代码
int main(int argc, char **argv) {
    // std::vector<bool> vec(?, ?);// TODO: 正确调用构造函数

    std::vector<bool> vec(100, true);  // 创建100个元素，全部初始化为true    
    ASSERT(vec[0], "Make this assertion pass.");
    ASSERT(vec[99], "Make this assertion pass.");
    ASSERT(vec.size() == 100, "Make this assertion pass.");
    // NOTICE: 平台相关！注意 CI:Ubuntu 上的值。
    std::cout << "sizeof(std::vector<bool>) = " << sizeof(std::vector<bool>) << std::endl;
    // ASSERT(sizeof(vec) == ?, "Fill in the correct value.");

    // vector对象本身的大小（通常24或32字节），不是元素总大小
    ASSERT(sizeof(vec) == sizeof(std::vector<bool>), "Fill in the correct value.");
            
    {
        vec[20] = false;
        ASSERT(!vec[20], "Fill in `vec[20]` or `!vec[20]`.");
    }
    {
        vec.push_back(false);
        ASSERT(vec.size() == 101, "Fill in the correct value.");
        ASSERT(!vec[100], "Fill in `vec[100]` or `!vec[100]`.");
    }
    {
        auto ref = vec[30];  // ref是std::vector<bool>::reference类型
        ASSERT(ref, "Fill in `ref` or `!ref`");
        ref = false;         // 通过代理对象修改值
        ASSERT(!ref, "Fill in `ref` or `!ref`");
        // THINK: WHAT and WHY?
        // ref是代理对象，修改ref会影响底层vector的值
        ASSERT(!vec[30], "Fill in `vec[30]` or `!vec[30]`.");
    }
    return 0;
}


/*
什么是模板特化？

就是既用模板写了一个函数，又将模板T换成了特殊的类型如int


我来帮你完成这个关于std::vector<bool>特化的练习。std::vector<bool>是std::vector的一个特化版本，专门用于存储bool值。

方法思路
理解std::vector特化：它不是普通的vector，而是对bool类型的特化实现
内存优化：使用位压缩存储，每个bool只占1位而不是1字节
特殊行为：operator[]返回的是代理对象而不是bool引用


代码解释
1. 构造函数
std::vector<bool> vec(100, true);
创建100个元素的vector，所有元素初始化为true
内存占用：大约100/8 = 13字节（加上vector的开销）
2. 特殊行为
auto ref = vec[30];  // 不是bool&，而是std::vector<bool>::reference
ref = false;         // 通过代理对象修改值
vec[30]返回的不是bool&，而是代理对象
代理对象可以像bool一样使用，但实际上是引用特定的位
3. 内存优化
std::cout << "sizeof(std::vector<bool>) = " << sizeof(std::vector<bool>) << std::endl;
输出的是vector对象本身的大小（通常24或32字节）
不是元素的总大小，元素是位压缩存储的
std::vector的特殊性
与普通vector的区别
特性	std::vector	std::vector
存储	每个元素sizeof(T)	每个元素1位
operator[]	返回T&	返回代理对象
内存效率	正常	高度优化
引用类型	真正的引用	代理引用
代理对象的行为
std::vector<bool> vec{true, false, true};

// 这些是等价的
vec[0] = false;
bool b = vec[1];

// 但不能这样做（因为返回的不是真正的引用）
// bool& ref = vec[0];  // 错误！
// auto& ref = vec[0];   // 错误！

// 应该这样
auto ref = vec[0];      // std::vector<bool>::reference
ref = false;            // 修改成功
常见问题
不能获取元素地址：因为元素是位压缩的
不能使用普通引用：需要代理引用
某些算法不兼容：需要特殊处理
实际应用
// 创建大型布尔数组（内存高效）
std::vector<bool> bitmap(1000000, false);  // 约125KB内存

// 普通bool数组（内存浪费）
std::vector<bool> normal_vec(1000000, false);  // 约1MB内存（如果按bool存储）

// 位操作
for (int i = 0; i < 1000000; i += 2) {
    bitmap[i] = true;  // 设置偶数位
}

// 统计true的数量
int count = 0;
for (bool b : bitmap) {  // 注意：这里会有代理对象的转换
    if (b) count++;
}
注意事项
性能权衡：位操作比直接访问慢，但节省内存
平台依赖性：具体实现可能不同
C++20改进：引入了std::vector<bool>::iterator的改进
测试验证
程序运行后会通过所有测试：

初始化和访问正确
修改操作正确
代理对象行为正确
大小计算正确
这个练习展示了C++模板特化的强大功能，以及如何为特定类型提供优化的实现。std::vector<bool>是一个经典的特化案例，在需要大量布尔值且内存受限的场景中非常有用。
*/